package oneDay;

import java.util.ArrayList;
import java.util.List;

/**
 *
 *给你一个正整数 n。
 *
 * 如果一个二进制字符串 x 的所有长度为 2 的
 * 子字符串
 * 中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。
 *
 * 返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。
 *
 *
 *
 * 示例 1：
 *
 * 输入： n = 3
 *
 * 输出： ["010","011","101","110","111"]
 *
 * 解释：
 *
 * 长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。
 *
 * 示例 2：
 *
 * 输入： n = 1
 *
 * 输出： ["0","1"]
 *
 * 解释：
 *
 * 长度为 1 的有效字符串有："0" 和 "1"。
 */
public class middle3211 {


    public List<String> res;

    /**
     *  输入一个n位数返回 0 和 1  组合n位数的所有可能
     * @param n
     * @return
     */
    public List<String> validStrings(int n) {
        res = new ArrayList<>();
        dfs("",n);
        return res;
    }

    private void dfs(String str,int n) {
        if(str.length()==n){
            res.add(str);
            return;
        }
        if(str.endsWith("0")){
            dfs(str+"1",n);
        }else{
            dfs(str+"0",n);
            dfs(str+"1",n);
        }
    }


}
